Link List
Q11.
Consider the C code fragment given below. typedef struct node { int data; node* next ; } node; void join (node* m, node* n) { node* p=n ; while (p->next ! =NULL){ p = p -> next ; } p-> next = m; } Assuming that m and n point to valid NULL- terminated linked lists, invocation of join willQ12.
An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum isQ14.
An algorithm performs (log N)^{1/2} find operations, N insert operations, (log N)^{1/2} delete operations, and (log N)^{1/2} decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?Q15.
The following steps in a linked list p = getnode() info(p) = 10 next (p) = list list = p result in which type of operation?Q16.
Consider a single linked list where F and L are pointers to the first and last elements respectively of the linked list. The time for performing which of the given operations depends on the length of the linked list?Q17.
Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?Q18.
The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution? struct node {int value; struct node *next;); void rearrange (struct node *list) { struct node *p, *q; int temp; if (!list || !list -> next) return; p = list; q = list -> next; while (q) { temp = p -> value; p -> value = q -> value; q -> value = temp; p = q -> next; q = p ? p -> next : 0; } }Q20.
Suppose there are \left \lceil log n \right \rceil sorted lists of \left \lfloor n/log n \right \rfloor elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)